//最后一块石头的重量二  力扣1049
//01背包
class Solution {
public:
	int lastStoneWeightII(vector<int>& stones) {
		int sum = 0;
		for(int i = 0; i < stones.size(); i++)
			sum += stones[i];
		
		int target = sum-(sum/2);
		vector<int> dp(target+1);
		
		for(int i = stones[0]; i < dp.size(); i++)
			dp[i] = stones[0];
		
		for(int i = 1; i < stones.size(); i++)
		{
			for(int j = target; j >= stones[i]; j--)
			{
				dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);
			}
		}
		return abs(dp[target]-(sum-dp[target]));
	}
};
